import java.util.HashMap;
import java.util.Map;

public class Test {
    /*
    题目 1 : 旋转图像
     */
    //给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
    //你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。
    // 请不要 使用另一个矩阵来旋转图像。
    //自己的思路：矩阵旋转 90°， 行变列，列变行，并且两者的行数 + 列数 = n - 1
    //所以只要创建一个新的矩阵，最后再把这个矩阵复制给旧矩阵即可！
    public void rotate1(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix0 = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix0[j][n - 1 - i] = matrix[i][j];
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = matrix0[i][j];
            }
        }
    }

    //能不能试着在原地修改呢？
    //原地旋转
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n/2; i++){
            for(int j = 0; j < (n + 1)/2; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;;
            }
        }
    }

    //通过翻转的方法
    //先水平翻转： (i,j) -> (n - 1 - i,j)
    //再对角线翻转：(n - 1 - i,j) -> (j,n - 1 - i)
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int temp = 0;
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < n; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - i][j];
                matrix[n - 1 - i][j] = temp;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    /*
    题目 2 ：螺旋数组Ⅱ
     */
    //给你一个正整数 n ，生成一个包含 1 到 n2 所有元素
    // 且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
    //思路： 模拟矩阵的生成过程！
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int up = 0;
        int bottom = n - 1;
        int left = 0;
        int right = n - 1;
        int num = 1;
        while(num <= n * n){
            for(int i = left; i <= right; i++ ){
                matrix[up][i] = num++;
            }
            up++;

            for(int i = up; i <= bottom; i++){
                matrix[i][right] = num++;
            }
            right--;

            for(int i = right; i >= left; i--){
                matrix[bottom][i] = num++;
            }
            bottom--;

            for(int i = bottom; i >= up; i--){
                matrix[i][left] = num++;
            }
            left++;
        }
        return matrix;
    }

    /*
    题目 3：字符串相加
     */
    //给定两个字符串形式的非负整数num1 和num2，计算它们的和并同样以字符串形式返回。
    //你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。
    //思路：模仿数学上的竖式计算
    public static String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }



    /*
    题目 4 ：单词规律
     */
    //给定一种规律 pattern和一个字符串s，判断 s是否遵循相同的规律。
    //这里的遵循指完全匹配，例如，pattern里的每个字母和字符串s中的每个非空单词之间存在着双向连接的对应规律。
    //这个解法太牛了！
    public static boolean wordPattern(String pattern, String s) {
        String[] str = s.split(" ");
        if(pattern.length() != str.length){
            return false;
        }

        Map<Object, Integer> map = new HashMap<>();
//对于 put 方法 ：如果key不存在，插入成功，返回null；如果key存在，则返回前一次 put 所对应的value,并且新的value 会替换旧的 value
        //这里得用 Integer ，如果是 int 会用到 Integer.valueOf(int) ，会受到[-128,127]的影响
        for(Integer i = 0; i < str.length; i++){
            char ch = pattern.charAt(i);
            if(map.put(ch,i) != map.put(str[i],i)){
                return false;
            }
        }
        return true;
    }
    public static void main1(String[] args) {
        String str1 = "abadd";
        String str2 = "dog cat cat dog dog";
        boolean ret = wordPattern(str1, str2);
        System.out.println(ret);
    }

    public static void main(String[] args) {
        Map<Character,Integer> map = new HashMap<>();
        System.out.println(map.put('A',1));
        int b = map.put('A',2);
        System.out.println(b);
        System.out.println(map.put('A',3));
        System.out.println(map.put('A',4));//返回前一次 put 的value，并把 value 从 3 改到 4！！
        //返回值为
        //null
        //1
        //2
        //3
        System.out.println(map.get('A'));
    }
    
}
